package com.zyk.leetcode;

import java.util.*;

/**
 * @author zhangsan
 * @date 2021/5/1 10:31
 */
public class C787 {


    private int[][] graph;
    private boolean[] visited;
    private int res = Integer.MAX_VALUE;

    public int findCheapestPrice2(int n, int[][] flights, int src, int dst, int K) {
        K = Math.min(K, n - 2);

        this.graph = new int[n][n];
        for (int[] flight : flights) {
            graph[flight[0]][flight[1]] = flight[2];
        }

        this.visited = new boolean[n];
        // 开始深度优先遍历，注意：这里传 K + 1，这是因为 K 次经停，总共 K + 1 个站
        dfs(src, dst, K + 1, 0);

        if (res == Integer.MAX_VALUE) {
            return -1;
        }
        return res;
    }


    /**
     * 从 src 出发，到 dst 为止，最多经过 k 站（这里 k 包括 src）
     *
     * @param src  起点站
     * @param dst  终点站
     * @param k    经过的站点数限制
     * @param cost 已经花费的价格
     */
    private void dfs(int src, int dst, int k, int cost) {
        if (src == dst) {
            res = cost;
            return;
        }

        if (k == 0) {
            return;
        }

        for (int i = 0; i < graph[src].length; i++) {
            if (graph[src][i] > 0) {
                if (visited[i]) {
                    continue;
                }

                // 剪枝：跳过可能产生较高费用的路径，从而选出最少价格
                if (cost + graph[src][i] > res) {
                    continue;
                }

                visited[i] = true;
                dfs(i, dst, k - 1, cost + graph[src][i]);
                visited[i] = false;
            }
        }
    }



    public static class Graph {

        public Graph.Node head;
        public HashMap<Integer, Node> nodes = new HashMap<>();
        public HashSet<Graph.Edge> edges = new HashSet<>();

        public boolean add(int value) {
            if (nodes.containsKey(value)) {
                return false;
            }
            Graph.Node node = new Graph.Node(value);
            if (head == null) {
                head = node;
            }
            nodes.put(value, node);
            return true;
        }

        public boolean connect(int weight, int fromValue, int toValue) {
            if (!nodes.containsKey(fromValue)) {
                add(fromValue);
            }
            if (!nodes.containsKey(toValue)) {
                add(toValue);
            }
            Graph.Node from = nodes.get(fromValue);
            Graph.Node to = nodes.get(toValue);
            connectProcess(from, to, weight);
            return true;
        }

        public boolean connect(Graph.Node from, Graph.Node to, int weight) {
            connectProcess(from, to, weight);
            return true;
        }

        private void connectProcess(Graph.Node from, Graph.Node to, int weight) {
            Graph.Edge edge = new Graph.Edge(weight, from, to);
            if (this.edges.contains(edge)) {
                return;
            }
            from.nexts.add(to);
            from.out++;
            to.in++;

            from.edges.add(edge);
            this.edges.add(edge);
        }

        @Override
        public String toString() {
            return "Graph{" +
                    "\n\thead=" + head +
                    ", \n\tnodes=" + nodes +
                    ", \n\tedges=" + edges +
                    "\n}";
        }

        public static class Node {
            public int value;
            public int in;
            public int out;
            public List<Node> nexts = new ArrayList<>();
            public List<Graph.Edge> edges = new ArrayList<>();

            public Node(int value) {
                this.value = value;
            }

            @Override
            public String toString() {
                return "Node{" +
                        "value=" + value +
                        ", in=" + in +
                        ", out=" + out +
                        '}';
            }
        }

        public static class Edge {

            public int weight;
            public Graph.Node from;
            public Graph.Node to;

            public Edge(int weight, Graph.Node from, Graph.Node to) {
                this.weight = weight;
                this.from = from;
                this.to = to;
            }

            @Override
            public String toString() {
                return "Edge{" +
                        "weight=" + weight +
                        ", from=" + from.value +
                        ", to=" + to.value +
                        '}';
            }

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
                Graph.Edge edge = (Graph.Edge) o;
                return weight == edge.weight &&
                        Objects.equals(from, edge.from) &&
                        Objects.equals(to, edge.to);
            }

            @Override
            public int hashCode() {
                return Objects.hash(weight, from, to);
            }
        }

    }


    public static class GraphGenerator {
        public static Graph create(int[][] matrix) {
            Graph graph = new Graph();
            if (matrix == null || matrix.length == 0) {
                return graph;
            }
            for (int[] integers : matrix) {
                int weight = integers[2];
                int fromValue = integers[0];
                int toValue = integers[1];
                graph.connect(weight, fromValue, toValue);
            }
            return graph;
        }
    }

    public static int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        Graph graph = GraphGenerator.create(flights);
        Graph.Node srcNode = graph.nodes.get(src);
        Graph.Node dstNode = graph.nodes.get(dst);
        int r = dfs2(srcNode, dstNode, K);
        return r == Integer.MAX_VALUE ? -1 : r;
    }

    public static int dfs2(Graph.Node src, Graph.Node dst, int k) {
        HashSet<Graph.Node> set = new HashSet<>();
        return dfsProcess(src, set, dst, k + 1, 0);
    }

    private static int dfsProcess(Graph.Node cur, HashSet<Graph.Node> set, Graph.Node dst, int rest, int cost) {
        if (set.contains(cur)) {
            return Integer.MAX_VALUE;
        }
        if (cur == dst) {
            return cost;
        }
        if (rest == 0) {
            return Integer.MAX_VALUE;
        }
        set.add(cur);
        int min = Integer.MAX_VALUE;
        for (Graph.Edge edge : cur.edges) {
            min = Math.min(min, dfsProcess(edge.to, set, dst, rest - 1, cost + edge.weight));
        }
        set.remove(cur);
        return min;
    }


    // for test
    public static void main(String[] args) {
        int n = 3, src = 0, dst = 2, k = 1;
        int[][] edges = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}};
        System.out.println(findCheapestPrice(n, edges, src, dst, k));
//        System.out.println(findCheapestPrice2(n, edges, src, dst, k));
    }

}
